# 定义一个二叉树的结点
class BinaryTreeNode(object):
    def __init__(self):
        self.data = '#'  # '#'代表空结点
        self.LeftChild = None
        self.RightChild = None


# 定义一个二叉树
class TreeState(object):
    def __init__(self, BinaryTreeNode, VistitedFlag):
        self.BinaryTreeNode = BinaryTreeNode
        self.VisitedFlag = VistitedFlag


# 定义一个二叉树操作的类
class BinaryTree(object):
    # 创建二叉树
    def CreateBinaryTree(self, Root):
        data = input('->')
        if data == '!':
            return
        if data == '#':
            root = None
        else:
            Root.data = data
            Root.LeftChild = BinaryTreeNode()
            self.CreateBinaryTree(Root.LeftChild)
            Root.RightChild = BinaryTreeNode()
            self.CreateBinaryTree(Root.RightChild)

    # 遍历二叉树一个结点
    def VisitBinaryTreeNode(self, BinaryTreeNode):
        # 值为#的结点代表空结点
        if BinaryTreeNode.data != '#':
            print(BinaryTreeNode.data, end='')

    # 先序遍历递归
    def PreOrder(self, Root):
        if Root is not None:
            self.VisitBinaryTreeNode(Root)
            self.PreOrder(Root.LeftChild)
            self.PreOrder(Root.RightChild)

    # 中序遍历递归
    def InOrder(self, Root):
        if Root is not None:
            self.InOrder(Root.LeftChild)
            self.VisitBinaryTreeNode(Root)
            self.InOrder(Root.RightChild)

    # 后序遍历递归
    def PostOrder(self, Root):
        if Root is not None:
            self.PostOrder(Root.LeftChild)
            self.PostOrder(Root.RightChild)
            self.VisitBinaryTreeNode(Root)

    # 获取值为val的结点
    def getVal(self, Root, val):
        if Root is not None:
            self.getVal(Root.LeftChild, val)
            self.getVal(Root.RightChild, val)
            if Root.data == val:
                Root.data = 'Z'
    def changeVal(self,Root,val):
        if Root is not None:
            self.changeVal(Root.LeftChild, val)
            self.changeVal(Root.RightChild, val)
            if Root.data == val:
                Root.RightChild = 'K'

bTN = BinaryTreeNode()  # 创建一个空结点
bT = BinaryTree()   # 创建一个二叉树
bT.CreateBinaryTree(bTN)
bT.PreOrder(bTN)
print()
bT.InOrder(bTN)
print()
bT.PostOrder(bTN)
print()
bT.getVal(bTN, 'F')
bT.PreOrder(bTN)
print()
bT.changeVal(bTN, 'G')
bT.PreOrder(bTN)







